package 简单.其他;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
 * 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
 */
public class 词典中最长的单词_720 {

    public static void main(String[] args) {

        String[] words = {"k", "lg", "it", "oidd", "oid", "oiddm", "kfk", "y", "mw", "kf", "l", "o", "mwaqz", "oi", "ych", "m", "mwa"};

        System.out.println(longestWord(words));

        System.out.println("ab".compareTo("ac"));

    }

    /**
     * 用个set存储每个单词是否存在
     * 因为每个单词都是从一个字母一个字母加上去的，可以进行判断
     *
     * @param words
     * @return
     */
    public static String longestWord(String[] words) {
        Set<String> set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        // 长度相等的字典序小的排前面
        Arrays.sort(words, (o1, o2) -> o1.length() == o2.length() ? o1.compareTo(o2) : o2.length() - o1.length());

        for (String word : words) {
            boolean flag = true;
            for (int i = 1; i <= word.length(); i++) {
                if (!set.contains(word.substring(0, i))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return word;
            }
        }
        return "";
    }

    /**
     * 有自带的compareTo方法使用
     *
     * @param first
     * @param secend
     * @return
     */
    public static int alphabetOrder(String first, String secend) {
        for (int i = 0; i < first.length(); i++) {
            if (first.charAt(i) > secend.charAt(i)) {
                return -1;
            } else if (first.charAt(i) < secend.charAt(i)) {
                return 1;
            }
        }
        return 0;
    }

    // TODO 字典树？？？

}
